﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace Commons.Utils
{
	[Serializable]
	public class RangeDictionary<K, V> : IEnumerable<KeyValuePair<K, V>> where K : IComparable
	{
		private SortedDictionary<K, V> list = new SortedDictionary<K, V>();
		private List<K> sortedList =  new List<K>();
		
		private bool useLowerLimits;
		private bool needSort;

		public RangeDictionary()
			: this(false)
		{
			needSort = false;
		}

		public RangeDictionary(bool useLowerLimits)
		{
			this.useLowerLimits = useLowerLimits;
		}

		public System.Collections.Generic.SortedDictionary<K,V>.ValueCollection Values
		{
			get 
			{
				return this.list.Values;
			}
		}

		public int Count
		{
			get
			{
				return list.Count;
			}
		}

		public void Add(K key, V value)
		{
			list.Add(key, value);
			sortedList.Add(key);
			needSort = true;
		}

		public V this[int index]
		{
			get {
				if( needSort )
				{
					needSort = false;
					sortedList.Sort();
				}
				
				V output;
				list.TryGetValue(sortedList[index],out output);
				return output;
			}
		}

		public V Get(K key)
		{
			int index = BinarySearch(key);
			return index >= 0 && index < list.Count ? this[index] : default(V);
		}

		private int BinarySearch(K key)
		{
			
			if( needSort )
			{
				needSort = false;
				sortedList.Sort();
			}
			
			int lo = 0;
			int hi = sortedList.Count - 1;
			while (lo <= hi)
			{
				int i = lo + ((hi - lo) >> 1);
				int order;
				if (sortedList[i] == null)
				{
					order = (key == null) ? 0 : -1;
				}
				else
				{
					order = sortedList[i].CompareTo(key);
				}

				if (order == 0)
				{
					return i;
				}

				if (order < 0)
				{
					lo = i + 1;
				}
				else
				{
					hi = i - 1;
				}
			}

			return useLowerLimits ? hi : lo;
		}

		IEnumerator IEnumerable.GetEnumerator()
		{
			return this.GetEnumerator();
		}

		public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
		{
			return list.GetEnumerator();
		}
	}
}
